/*
 * @lc app=leetcode.cn id=210 lang=typescript
 *
 * [210] 课程表 II
 */

// @lc code=start
function findOrder(numCourses: number, prerequisites: number[][]): number[] {
  const graph: number[][] = new Array(numCourses).fill(0).map(() => []);
  const degree: number[] = new Array(numCourses).fill(0);

  // 建模
  for (let [to, from] of prerequisites) {
    graph[from].push(to);
    degree[to]++;
  }

  const queue = [];
  for (let i = 0; i < numCourses; i++) {
    degree[i] === 0 && queue.push(i);
  }

  const result = [];
  while (queue.length) {
    let v = queue.shift();
    result.push(v);
    for (let w of graph[v]) {
      degree[w]--;
      degree[w] === 0 && queue.push(w);
    }
  }
  // 长度一致表示无环，输出拓扑排序结果，否则有环，输出空数组
  return result.length === numCourses ? result : [];
}
// @lc code=end
